package com.atguigu.binaryTree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

public class TheBiggestWidthOfBinaryTree {
    public static int findTheWidthOfBinaryTree(TreeNode root){
        if(root==null) return 0;
        Map<TreeNode,Integer> map=new HashMap<>();
        Queue<TreeNode> queue=new LinkedList<>();
        map.put(root,1); //根节点，层数为1
        queue.offer(root);
        int curLevel=1; // 当前节点所在层数
        int curLevelNodes=0; //当前层节点数量
        int max=Integer.MIN_VALUE;
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            int curNodeLevel=map.get(cur); //获取当前节点所在层数
            if(curLevel==curNodeLevel){
                curLevelNodes++;
            }else{
                max=Math.max(curLevelNodes,max);
                curLevel++; //不是同一层
                curLevelNodes=1; //当前节点个数重置为1
            }
            if(cur.left!=null){
                map.put(cur.left,curNodeLevel+1);
                queue.add(cur.left);
            }
            if(cur.right!=null){
                map.put(cur.right,curNodeLevel+1);
                queue.add(cur.right);
            }
        }
        max=Math.max(max,curLevelNodes);
        return max;
    }
}
